home *** CD-ROM | disk | FTP | other *** search
/ Java 1996 August / Java - Summer 1996.iso / kaffe-0.2 / kaffe / gc.c < prev    next >
C/C++ Source or Header  |  1996-02-19  |  8KB  |  370 lines
  1. /*
  2.  * gc.c
  3.  * The garbage collector.
  4.  *
  5.  * Copyright (c) 1996 Systems Architecture Research Centre,
  6.  *           City University, London, UK.
  7.  *
  8.  * See the file "license.terms" for information on usage and redistribution
  9.  * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
  10.  *
  11.  * Written by Tim Wilkinson <tim@sarc.city.ac.uk>, February 1996.
  12.  */
  13.  
  14. /* #define    NOGC    /* Turn off garbage collection */
  15.  
  16. #define    DBG(s)
  17. #define    MDBG(s)
  18. #define    FDBG(s)
  19. #define    ADBG(s)
  20.  
  21. #include <assert.h>
  22. #include "gtypes.h"
  23. #include "object.h"
  24. #include "classMethod.h"
  25. #include "baseClasses.h"
  26. #include "lookup.h"
  27. #include "thread.h"
  28. #include "gc.h"
  29. #include "md.h"
  30.  
  31. extern thread* threadQhead[];
  32. extern classes* ThreadClass;
  33. extern strpair* finalpair;
  34. extern thread* finalman;
  35. extern thread* gcman;
  36.  
  37. static gcRef* refTable[GCREFTABLESZ];
  38. static int refTableIdx;
  39. static gcRef* freeRef;
  40. static gcRef* permList;
  41. static void* minGcMemory = (void*)-1;
  42. static void* maxGcMemory = (void*)0;
  43. static gcRef* garbageObjects;
  44. static unsigned int allocCount;
  45.  
  46. /* When's a good time to run the GC? Run it every 1000 allocations */
  47. #define    GCTRIGCOUNT            1000
  48.  
  49. static void markObject(object*);
  50. static void garbageCollect(void);
  51. static gcRef* validReference(object*);
  52.  
  53. /*
  54.  * Add an object into the garbage collection scheme.
  55.  */
  56. void
  57. add_object(object* o, bool perm)
  58. {
  59.     gcRef* table;
  60.     gcRef* ref;
  61.     int i;
  62.  
  63. #if defined(NOGC)
  64.     return;
  65. #endif
  66.  
  67.     /* Reset min and max memory pointers */
  68.     if ((void*)o < minGcMemory) {
  69.         minGcMemory = (void*)o;
  70.     }
  71.     if ((void*)o > maxGcMemory) {
  72.         maxGcMemory = (void*)o;
  73.     }
  74.  
  75.     ref = freeRef;
  76.     if (ref != 0) {
  77.         freeRef = freeRef->next;
  78.     }
  79.     else {
  80.         assert(refTableIdx < GCREFTABLESZ);
  81.         table = (gcRef*)malloc(sizeof(gcRef) * GCREFMAX);
  82.         assert(table != 0);
  83.  
  84.         /* Build into free list */
  85.         for (i = 0; i < GCREFMAX; i++) {
  86.             table[i].flags = GC_FREE;
  87.             table[i].next = &table[i+1];
  88.             table[i].idx = i + (refTableIdx * GCREFMAX);
  89.         }
  90.         table[GCREFMAX-1].next = 0;
  91.         freeRef = &table[1];
  92.         ref = &table[0];
  93.  
  94.         refTable[refTableIdx] = table;
  95.         refTableIdx++;
  96.     }
  97.  
  98.     assert(ref->flags == GC_FREE);
  99.  
  100.     /* Make ref point at object, and object point at ref */
  101.     o->idx = ref->idx;
  102.     ref->obj = o;
  103.     ref->flags = GC_UNMARK;
  104.     ref->next = 0;
  105.  
  106.     /* If object is permenant, put it on the perm list */
  107.     if (perm == true) {
  108.         ref->next = permList;
  109.         permList = ref;
  110.     }
  111.  
  112. ADBG(    printf("Adding new object 0x%x at index %d - %s\n", o, o->idx, o->type ? o->type->name : "<none>"); )
  113.  
  114.     if (++allocCount % GCTRIGCOUNT == 0) {
  115.         invokeGarbageCollector();
  116.     }
  117. }
  118.  
  119. /*
  120.  * Invoke the garbage collector (if we have one)
  121.  */
  122. void
  123. invokeGarbageCollector(void)
  124. {
  125.     if (gcman != 0) {
  126.         lockMutex(&gcman->obj);
  127.         signalCond(&gcman->obj);
  128.         unlockMutex(&gcman->obj);
  129.     }
  130. }
  131.  
  132. /*
  133.  * Is object reference a real object?
  134.  */
  135. static
  136. inline
  137. gcRef*
  138. validReference(object* o)
  139. {
  140.     gcRef* ref;
  141.  
  142.     /* Validate object address.  To be a real object it must lie
  143.        inside the malloced memory pool, and its index must refer to
  144.        a GC entry which refers to it. */
  145.     if ((void*)o < minGcMemory || (void*)o > maxGcMemory) {
  146.         return (0);
  147.     }
  148.     ref = refTable[(o->idx / GCREFMAX) % GCREFTABLESZ];
  149.     if (ref == 0) {
  150.         return (0);
  151.     }
  152.     ref = &ref[o->idx % GCREFMAX];
  153.     if (ref->obj != o) {
  154.         return (0);
  155.     }
  156.  
  157.     /* Stop when we reach a mark */
  158.     if (ref->flags != GC_UNMARK) {
  159.         return (0);
  160.     }
  161.  
  162.     return (ref);
  163. }
  164.  
  165. /*
  166.  * Garbage collect objects.
  167.  */
  168. static
  169. void
  170. garbageCollect(void)
  171. {
  172.     int i;
  173.     thread* tid;
  174.     object** ptr;
  175.     gcRef* ref;
  176.     int j;
  177.     gcRef* table;
  178.  
  179. #if defined(NOGC)
  180.     return;
  181. #endif
  182.  
  183. DBG(    printf("Garbage collecting ... \n");                )
  184.  
  185.     /* Scan the permentant object list */
  186.     for (ref = permList; ref != 0; ref = ref->next) {
  187.         markObject(ref->obj);
  188.     }
  189.  
  190.     /* Scan each thread */
  191.     for (i = MIN_THREAD_PRIO; i <= MAX_THREAD_PRIO; i++) {
  192.         for (tid = threadQhead[i]; tid != 0; tid = tid->next) {
  193.             markObject(&tid->obj);
  194.             for (ptr = (object**)tid->eetop->restorePoint; ptr < (object**)tid->eetop->stackEnd; ptr++) {
  195.                 markObject(*ptr);
  196.             }
  197.         }
  198.     }
  199.  
  200.     /* Now look through object table for objects which have not
  201.        been marked.  These can be freed. */
  202.     for (j = 0; j < refTableIdx; j++) {
  203.         table = refTable[j];
  204.         for (i = 0; i < GCREFMAX; i++) {
  205.             switch(table[i].flags) {
  206.             case GC_GARBAGE:
  207.             case GC_FREE:
  208.                 break;
  209.  
  210.             case GC_MARK:
  211.                 table[i].flags = GC_UNMARK; /* For next time */
  212.                 break;
  213.  
  214.             case GC_UNMARK:
  215.                 /* Object not marked - free */
  216.                 table[i].flags = GC_GARBAGE;
  217.                 table[i].next = garbageObjects;
  218.                 garbageObjects = &table[i];
  219.                 break;
  220.             }
  221.         }
  222.     }
  223.  
  224. DBG(    printf("Garbage collecting ... done.\n");            )
  225. }
  226.  
  227. /*
  228.  * Given an object, mark it and follow any object references it contains.
  229.  */
  230. static
  231. void
  232. markObject(object* o)
  233. {
  234.     object** child;
  235.     classes* class;
  236.     fields* fld;
  237.     int i;
  238.     gcRef* ref;
  239.  
  240.     /* Null object reference */
  241.     if (o == 0) {
  242.         return;
  243.     }
  244.  
  245.     /* Invalid object or already visited? */
  246.     ref = validReference(o);
  247.     if (ref == 0) {
  248.         return;
  249.     }
  250.  
  251. MDBG(    printf("Marking object 0x%x at index %d - %s\n", o, o->idx, o->type ? o->type->name : "<none>"); )
  252.  
  253.     /* Mark this object */
  254.     ref->flags = GC_MARK;
  255.  
  256.     class = o->type;
  257.  
  258.     /* Mark the class object */
  259.     markObject(&class->head);
  260.  
  261.     /* If this is a class object, mark the static fields and constants */
  262.     if (class == ClassClass) {
  263.         class = (classes*)o;
  264.         markObject(&class->superclass->head);
  265.         child = (object**)class->staticFields;
  266.         for (i = 0; i < class->sfsize; i++) {
  267.             markObject(child[i]);
  268.         }
  269.         if (class->constants != 0) {
  270.             child = (object**)class->constants->data;
  271.             for (i = class->constants->size - 1; i >= 0; i--) {
  272.                 markObject(child[i]);
  273.             }
  274.         }
  275.     }
  276.     /* Otherwise, a normal object or an array of objects then ... */
  277.     else if (o->type->sig[0] == 'L' || o->type->sig[1] == 'L') {
  278.         assert(o->type->sig[0] == 'L' || o->type->sig[0] == '[');
  279.         child = (object**)o->data;
  280.         for (i = 0; i < o->size; i++) {
  281.             markObject(child[i]);
  282.         }
  283.     }
  284. }
  285.  
  286. /*
  287.  * Finaliser.
  288.  * Finalises any objects which have been garbage collected before
  289.  *   deleting them.
  290.  */
  291. void
  292. finaliserMan(void)
  293. {
  294.     object* obj;
  295.     gcRef* ref;
  296.     void* func;
  297.  
  298.     /* All threads start with interrupts disabled */
  299.     intsRestore();
  300.  
  301.     lockMutex(¤tThread->obj);
  302.     for (;;) {
  303.         while (garbageObjects) {
  304.             ref = garbageObjects;
  305.             garbageObjects = garbageObjects->next;
  306.             assert(ref->flags == GC_GARBAGE);
  307.             ref->next = 0;
  308.             obj = ref->obj;
  309.  
  310.             /* Finalise object if necessary */
  311.             if (obj->final == 0) {
  312.                 obj->final = 1;
  313.                 func = findMethod(obj->type, finalpair);
  314.                 assert(func != 0);
  315.                 CALL_KAFFE_FUNCTION_VARARGS(func, obj, 0, 0);
  316.                 /* Don't free it cause it might live */
  317.                 ref->flags = GC_UNMARK;
  318.                 continue;
  319.             }
  320.             /* Special handling for threads */
  321.             if (obj->type == ThreadClass) {
  322.                 thread* stiff = (thread*)obj;
  323.                 free(stiff->eetop->stackBase);
  324.                 free(stiff->eetop);
  325.             }
  326.             /* Don't handle classes yet */
  327.             else if (obj->type == ClassClass) {
  328.                 abort();
  329.             }
  330.  
  331.             /* Put entry onto freelist */
  332.             ref->flags = GC_FREE;
  333.             ref->next = freeRef;
  334.             freeRef = ref;
  335.  
  336.             /* Free the object */
  337. FDBG(            printf("Freeing object 0x%x(%d) %s\n", obj,
  338.                 ref->idx, obj->type->name);        )
  339.             free(obj);
  340.         }
  341.         waitCond(¤tThread->obj, -1);
  342.     }
  343. }
  344.  
  345. /*
  346.  * Garbage collector.
  347.  *  Run the garbage collector.
  348.  */
  349. void
  350. gcMan(void)
  351. {
  352.     /* All threads start with interrupts disabled */
  353.     intsRestore();
  354.  
  355.     lockMutex(¤tThread->obj);
  356.     for (;;) {
  357.         waitCond(¤tThread->obj, -1);
  358.  
  359.         /* Run the garbage collector */
  360.         garbageCollect();
  361.  
  362.         /* If there's garbage, finalise it */
  363.         if (garbageObjects != 0 && finalman != 0) {
  364.             lockMutex(&finalman->obj);
  365.             signalCond(&finalman->obj);
  366.             unlockMutex(&finalman->obj);
  367.         }
  368.     }
  369. }
  370.